The present invention relates to transforming a color from a first color space to a second color space. It finds particular application in conjunction with interpolating within a three-dimensional lookup table and will be described with particular reference thereto. It will be appreciated, however, that the invention is also amenable to other like applications.
Color correction or transformation of color images is performed to convert images from one color space to another. Images may be represented using a device independent color space or a device dependent color space. Device independent color spaces represent color images independent from particular input and output devices so as to enable independent color imaging between input and output devices. Generally, a color image is transformed to a device dependent color space of an output device before the color image is rendered to ensure that the colorimetry of the original image is consistent with its reproduction. Such a transformation is performed regardless of whether the original image is defined in a device dependent color space or in a device independent color space. Closed systems that consist, for example, of a scanner and a printer that are not interconnected with external devices do not require an original color image to be transformed to a device independent color space. Such closed systems have color transformation systems that generate a color image represented by a first color space and subsequently convert that color space to a second color space before reproduction. Color transformation systems capable of independent color imaging represent color images in a third or a device independent color space which is readily transferable between a plurality of image output devices.
Color images can be generated by an input image terminal such as a scanner or a color image creation program operating on a color workstation. Color images processed by a scanner or a workstation consists of a two-dimensional array of picture elements (pixels). The color of each pixel of an image may be represented using a plurality of color spaces. Scanner output is commonly transformed to a color space of tristimulus values, for example, additive primaries red, green and blue (RGB) color space. These values are typically a linear transformation of the standard XYZ coordinates of CIE color space, or a corrected transform of those values. In the case of computer generated images, the computer workstation is operated by a user to create, edit, or view “softcopy” color images on the color monitor of the workstation. Colors selected by the user at the user interface of a workstation can also be defined in a color space of tristimulus values such as additive primaries RGB.
An image generated by an image input terminal must be converted to subtractive primaries cyan, magenta, yellow and black (CMYK) or (simply the CMY) color space before being reproduced on an image output terminal such as a printer. CMY color space is typically used to represent the formulation of colored dyes, inks, or toners on paper. Printers typically operate by adding multiple layers of ink or colorant on each page. The response of the addition of colors by the printer tends to be relatively non-linear. Consequently, colors are defined for a particular printer and accordingly color spaces defined for a printer are device dependent. Thus, a printer receives information in a device independent color space from, for example, a workstation. The printer must then convert that information into its device dependent color space. There exist many different methods to convert between color spaces of images produced at a scanner or a workstation to a color space of images to be produced at a printer.
Color correction consists of mapping points from a three-dimensional color space to a three-or-more-dimensional color space. This mapping depends on the physical properties of a marking device or printer system which is typically nonlinear (as noted above). An effective approach to solving this problem is to use a coarse three-dimensional lookup table with interpolation. The lookup table provides an arbitrary mapping between different devices and the interpolation reduces the size of the table so that large amounts of memory are not required by the system to store a large number of sample points. In general, a lookup table contains values on a uniform grid for each of the three color coordinates of a color space. A common approach to interpolation is tri-linear interpolation which gives a linear weighting of all eight vertices. Alternatively, in tetrahedral interpolation the parallelepiped is divided into tetrahedra. The points within each tetrahedron are interpolated based on its four vertices. While tetrahedral interpolation is adequate for finding individual points at a lookup table of 163 nodes, it performs unnecessary computations when used with tables of 643 nodes or more.
More specifically, because color is defined with three (3) variables, a three-dimensional lookup table is commonly used. In RGB space, at a scanner or computer, space can be defined as three-dimensional with black at the origin of a three-dimensional coordinate system 0, 0, 0, and white at the maximum of a three dimensional coordinate system which in an 8-bit system, would be located at 255, 255, 255. Each of the three (3) axes radiating from the origin point, therefore, define red, green, and blue, respectively. A similar construct can be made for the printer, with axes representing cyan, magenta, and yellow. In the 8-bit system suggested, there will be, however, over 16 million possible colors (i.e., 2563), which are too many values for a 1:1 mapping of RGB to CMY within a reasonable amount of space. Accordingly, only a relatively small number of samples are conventionally used to do the mapping from RGB to CMY.
The lookup table is conventionally constructed using slow methods that combine measured data with mathematical modeling. The time required to construct such a table of size 163 ranges from several minutes to one or two hours, depending on the method used. Constructing a large table of size 2563 (where no interpolation is required) or even 643, requires 4096 or 64 times as long, respectively. For example, if it takes 1 second to compute an entry, it will take 68 minutes to compute the 4096 entries of a 163 table. At that rate, it will take 194 days to compute the 224=16,777,216 entries in a 2563 table, and 72 hours, 49 minutes to compute the 218=262,144 entries in a 643 table. Thus, computing a table at such high density using conventional techniques is impractical.
The present invention provides a new and improved method and apparatus which overcomes the above-referenced problems and others.